1. Technical Field
This invention relates to ad hoc networking application, in which a number of communications devices co-operate to form a communications network.
2. Related Art
There are two basic types, namely many-to-many communication, wherein the devices communicate with conventional fixed networks through interface or edge devices. The communications devices form nodes of a wireless network, allowing data to be relayed from an originating communications device to a destination communications device, by way of other communications devices. Such devices have a number of applications in circumstances where the communications devices are likely to be moving in unpredictable ways. A particular application scenario is a sensor network, in which data is collected from a network of mobile sensor devices, each of which is capable of taking measurements and relaying packets of data. Such devices are used by scientists taking measurements of the behaviour of the atmosphere, the sea, ice caps, lava flows or wildlife. The environments in which such devices are required to operate often have measurement points widely dispersed in both space and time. Some of the environments are hostile to human life. In some applications, such as the study of animal behaviour, human intervention could compromise the data. For these reasons the devices must be capable of operating autonomously, and transmitting the data they collect to a more convenient point using a wireless medium such as radio or sound. Moreover it is not usually possible to provide a continuous power supply, so the useful life of a device is primarily constrained by battery life.
Other applications for such ad hoc networks, to which the invention might be applied, include “tagging” technology for monitoring the health of patients and the elderly in the community, or of the location of people subject to court orders restricting their movements. More generally, ad hoc networks can be made up of wireless laptop computers or mobile telephones in close proximity to each other. Military personnel, police or other emergency services could also use the invention when attending an incident where there are insufficient channels for all the users to communicate directly with the fixed base stations provided in the vicinity. In these cases, more conventional communication devices could become part of ad hoc wireless networks, exploiting short range transmissions and device relays towards an identified base station, or fixed network device.
Many ad hoc routing protocols have been devised. Some of the most widely known are:    DSDV, described by C Perkins and P Bhagwat, Highly Dynamic Destination-Sequenced Distance-Node pair Routing (DSDV) for mobile computers, Proceedings of the SIGCOMM '94 Conference on Communications Architectures, Protocols and Applications, pages 234-244, August 1994    TORA, described by V D Park and M S Corson, A Highly Adaptive Distributed routing Algorithm for Mobile Wireless Networks, Proceedings of INFOCOM '97, pages 1405-1413, April 1997    DSR, described by D B Johnson, Routing in Ad hoc Networks of Mobile Hosts, Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158-163, December 1994    AODV, described by C Perkins, Ad hoc On Demand Distance Node pair (AODV) Routing, Internet-Draft, draft-ietf-manet-aodv-04.txt, October 1999DSDV maintains a routing table listing the next “hop” for each reachable destination. Routes are tagged with sequence numbers, with the most recently determined route, with the highest sequence number, being the most favoured. There are periodic updates of routes and sequence numbers. TORA discovers routes on demand and gives multiple routes to a destination. Route query and update packets are sent for each destination. Although routes are established fairly quickly, there are often routing loops, leading to dropped packets. DSR uses source routing, rather than hop-by-hop routing, so each packet has a complete route, listed in its header. This protocol uses route discovery and route maintenance, with nodes maintaining caches of source routes that have been learned or overheard. AODV combines route discovery and route maintenance with hop-by-hop routing. Route request packets create reverse routes for themselves back to their source devices. “Hello” messages are periodically transmitted by the devices, so that neighbours are aware of the state of local links.
A comparison of the performance of these protocols by J Broch, D A Maltz, D B Johnson, Y-C Hu, (“A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols”, Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, Mobicom '98, October 1998, Dallas, Tex.), has shown widely differing results in the size of routing overhead. The total overhead is greatest for TORA, and becomes unacceptably large for a network size of thirty source devices.
Moreover, all of these prior art protocols require large processor and memory capacities, and their protocols do not take account of the energy usage required. Energy usage, along with memory and processor capacity, are particularly important in sensor networks. These typically consist of very small, very cheap microprocessors, e.g. 16 bit, with 32 kilobytes of RAM. They also have a finite battery supply, which would be impractical to replace given the nature of the applications in which the sensors are to be used. It is therefore very important that any communication protocol is energy-efficient aware, and also pared to a minimum in communication overhead and memory usage. In other applications, battery and memory usage are also important considerations: a user would be unwilling to allow his mobile telephone to form part of such an ad hoc network if other users caused a significant drain on either of these resources whilst his own device was not actively engaged in a call.
A number of lightweight ad hoc routing protocols have been proposed. The work by Toh already discussed describes a wireless communication network, and a scheme to maximise the battery life of ad hoc devices in the network. S Singh, M Woo and C Raghavendra, have made a detailed study of power-conservation in ad hoc networks at the MAC and network layers (“Power-Aware Routing in Mobile Ad hoc Networks”. Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), (Dallas, Tex., October 1998)). They include schemes for devices to power-down in between expected transmissions, and they take into account device load as an important factor in power consumption. Their main concern is to prevent network partitioning when gaps appear in the network as a result of devices running out of battery power. Work by W B Heinzelman, A P Chandrakasan and H Balakrishnan considers sensor networks specifically. (“Energy-Efficient Routing Protocols for Wireless Microsensor Networks”, Proceedings of the 33rd International Conference on System Sciences (HICSS '00), January 2000). This work assumes variable device broadcast range. Their focus is on the use of clustering techniques to reduce bandwidth usage by, for example, data aggregation of similar data, and using predictable transmission times, coordinated by the cluster heads. This approach saves significant energy, compared with an always-on approach, but the routing side is simplistic and not fully developed. In particular, their experimental scenario assumes the devices could all broadcast to the base station if they chose to do so, which would not be realistic, in general, for sensor network applications. Work by A Cerpa, J elson, D Elstrin, L Girod, M Hamilton and J Zhao, refers to habitat monitoring as a driver for wireless communications technology, and focuses on power-saving by having devices switching themselves on and off according to whether they are in the vicinity of regions where interesting activity is expected, or detected by other devices. (“Habitat Monitoring: Application Driver for Wireless Communications Technology”, ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, Costa Rica, April 2001. Work by Y. Xu, J. Heidemann, and D. Estrin again focuses on using powered-down modes for devices to conserve power, based on whether payload data is predicted or not, and on the number of equivalent devices nearby that could be used for alternate routing paths. (“Adaptive energy-conserving routing for multihop ad hoc networks”, Tech. Rep. 527, USC/Information Sciences Institute, October, 2000) The assumption here is that the underlying routing will be based on conventional ad hoc routing protocols such as the AODV system already discussed. Sensor networks, however, typically would require a lighter weight approach to routing, where decisions are based on information from immediate neighbours only, and this knowledge needs to be conveyed succinctly, ideally as part of the packet headers for the actual data to be collected.
A lot of work has been done at the University of California and the Intel Berkeley Research Lab, to develop operating systems and networks for small ad hoc sensor devices, known as the Smartdust project, for which an operating system known as TinyOS has been developed (D E. Culler, J Hill, P Buonadonna, R Szewczyk, and A Woo. “A Network-Centric Approach to Embedded Software for Tiny Devices”. DARPA Workshop on Embedded Software. However, the routing scheme they refer to is not power-aware, but rather uses a hierarchical structure to find shortest paths to the sinks.
So, in summary, there are established routing protocols for ad hoc networks that are too resource-intensive for sensor networks and are not power-aware; there are power-aware metrics which have not been applied to ad hoc networks; there are power-aware strategies for ad hoc sensor networks that do not optimise the routing; and there is an extensive ad hoc sensor network project without power-aware routing. Note that none of his prior work refers to highly mobile ad hoc devices, of the kind to which this invention is particularly directed.
As already discussed, prior art routing mechanisms require far more memory and processing power than is suitable for lightweight environmental sensor devices, or assume all devices can communicate directly with the sinks. Also, only the full ad hoc protocols can cope with device mobility, and these require a large communication overhead.